class Solution(object):
    def superPow(self, a, b):
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        base = 1337
        a = a % base
        c = a
        a_set = {a: 0}
        index = 0
        while True:
            index += 1
            c = c * a % base
            if c not in a_set:
                a_set[c] = index
            else:
                base_index = a_set[c]
                add_index = index - base_index
                break
        n = len(b)
        for i in range(n):
            if b[n - 1 - i] == 0:
                b[n - 1 - i] = 9
            else:
                b[n - 1 - i] -= 1
                break
        index = 0
        while index < n:
            if b[index] == 0:
                index += 1
            else:
                break
        n = len(b)

        def search(s, k):
            while int(s) < add_index and k < n:
                s += str(b[k])
                k += 1
            if int(s) < add_index:
                return int(s)
            else:
                s = str(int(s) % add_index)
                return search(s, k)
        target = search('0', 0)
        for key in a_set:
            if a_set[key] == target:
                return key


data = Solution()
a = 2
b = [3]
print(data.superPow(a, b))
